	package 剑指offer;

public class _31从1到n整数中1出现的次数 {
	
	/*
	 * 求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次(11中个数1和十位1算2次),但是对于后面问题他就没辙了。
	 * ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）
	 */
	/*
	  *思路：若百位上数字为0，百位上可能出现1的次数由更高位决定(before*i)；若百位上数字为1，百位上可能出现1的次数
		不仅受更高位影响还受低位影响(before*i+after+1)；若百位上数字大于1，则百位上出现1的情况仅由更高位决定((before+1)*i)
	 */
	
	//暴力:从0开始遍历n,在遍历的时候,将其转换成String,在遍历String,利用charAt(j) ==1,进行判断是否需要count++
		public int NumberOf1Between1AndN_Solution3(int n) {
		 
		    int num = n;
		    int count = 0;// 计算数字中含有1的数字个数。
		    int strLen = 0;//每个数字的长度
		    for (int i = 0; i <= num; i++) {
		        String str = String.valueOf(i);
		        strLen = str.length();
		        for (int j = 0; j < strLen; j++) {
		            if (str.charAt(j) == '1') {
		                count++;
		            }
		        }
		    }
		 
		    return count;
		}

		/*
	设N = abcde ,其中abcde分别为十进制中各位上的数字。
	如果要计算百位上1出现的次数，它要受到3方面的影响：
	百位上的数字，百位以下（低位）的数字，百位以上（高位）的数字。
	① 如果百位上数字为0，百位上可能出现1的次数由更高位决定。比如：12013，则可以知道百位出现1的情况可能是：100~199，1100~1199,2100~2199，，...，11100~11199，一共1200个。可以看出是由更高位数字（12）决定，并且等于更高位数字（12）乘以 当前位数（100）。
	② 如果百位上数字为1，百位上可能出现1的次数不仅受更高位影响还受低位影响。比如：12113，则可以知道百位受高位影响出现的情况是：100~199，1100~1199,2100~2199，，....，11100~11199，一共1200个。和上面情况一样，并且等于更高位数字（12）乘以 当前位数（100）。但同时它还受低位影响，百位出现1的情况是：12100~12113,一共114个，等于低位数字（113）+1。
	③ 如果百位上数字大于1（2~9），则百位上出现1的情况仅由更高位决定，比如12213，则百位出现1的情况是：100~199,1100~1199，2100~2199，...，11100~11199,12100~12199,一共有1300个，并且等于更高位数字+1（12+1）乘以当前位数（100）。
	*/
/*	public int NumberOf1Between1AndN_Solution(int n) {
		long count = 0; // 1的个数
		long i = 1; // 当前位
		long current = 0,after = 0,before = 0;
		while((n / i) != 0) {
		before = n / (i * 10); // 高位
		current = (n / i) % 10; // 当前位
		after = n - (n / i) * i; // 低位
		if (current == 0)
		//如果为0,出现1的次数由高位决定,等于高位数字 * 当前位数
		count = count + before * i;
		else if(current == 1)
		//如果为1,出现1的次数由高位和低位决定,高位*当前位+低位+1
		count = count + before * i + after + 1;
		else if (current > 1)
		// 如果大于1,出现1的次数由高位决定,（高位数字+1）* 当前位数
		count = count + (before + 1) * i;
		//前移一位
		i = i * 10;
		} 
		return (int) count;
		
    }*/

	/**	层主只是以这个为例子 其实还是逐个位进行判断的
	 * //主要思路：设定整数点（如1、10、100等等）作为位置点i（对应n的各位、十位、百位等等），分别对每个数位上有多少包含1的点进行分析
	 *     //根据设定的整数位置，对n进行分割，分为两部分，高位n/i，低位n%i
	 *     //当i表示百位，且百位对应的数>=2,如n=31456,i=100，则a=314,b=56，此时百位为1的次数有a/10+1=32（最高两位0~31），每一次都包含100个连续的点，即共有(a%10+1)*100个点的百位为1
	 *     //当i表示百位，且百位对应的数为1，如n=31156,i=100，则a=311,b=56，此时百位对应的就是1，则共有a%10(最高两位0-30)次是包含100个连续点，当最高两位为31（即a=311），本次只对应局部点00~56，共b+1次，所有点加起来共有（a%10*100）+(b+1)，这些点百位对应为1
	 *     //当i表示百位，且百位对应的数为0,如n=31056,i=100，则a=310,b=56，此时百位为1的次数有a/10=31（最高两位0~30）
	 *     //综合以上三种情况，当百位对应0或>=2时，有(a+8)/10次包含所有100个点，还有当百位为1(a%10==1)，需要增加局部点b+1
	 *     //之所以补8，是因为当百位为0，则a/10==(a+8)/10，当百位>=2，补8会产生进位位，效果等同于(a/10+1)
	 *     -------------------------
	 *      最自然的想法莫过于直接遍历1到N，求出每个数中包含的1的个数，然后将这些个数相加就是总的 1 的个数。需要遍历 N 个数，每次计算 1 的个数需要 O(log10N)，该算法复杂度为 O(Nlog10N)。当数字N很大的时候，该算法会耗费很长的时间，应该还有更好的方法。
	 *
	 * 解： 我们可以从1位数开始分析，慢慢找寻规律。
	 *
	 * 当 N 为 1 位数时，对于 N>=1，1 的个数 f(N) 为1。
	 *
	 * 当 N 为 2 位数时，则个位上1的个数不仅与个位数有关，还和十位数字有关。
	 *
	 * 当 N=23 时，个位上 1 的个数有 1、11、21 共3个，十位上1的个数为10，11...19 共10个，所以 1 的个数 f(N) = 3+10 = 13。如果 N 的个位数 >=1，则个位出现1的次数为十位数的数字加1；如果 N 的个位数为0，则个位出现 1 的次数等于十位数的数字。
	 *
	 * 十位数上出现1的次数类似，如果N的十位数字等于1，则十位数上出现1的次数为各位数字加1；如果N的十位数字大于1，则十位数上出现1的次数为10。
	 *
	 * 当 N 为 3 位数时，同样分析可得1的个数。如 N=123，可得 1出现次数 = 13+20+24 = 57。
	 *
	 * 当 N 为 4,5...K 位数时，我们假设 N=abcde，则要计算百位上出现1的数目，则它受到三个因素影响：百位上的数字，百位以下的数字，百位以上的数字。
	 *
	 * 如果百位上数字为0，则百位上出现1的次数为更高位数字决定。如 N=12013，则百位出现1的数字有100~199， 1000~1199， 2100~2199...11100~111999 共 1200 个，等于百位的更高位数字(12)*当前位数(100)。
	 *
	 * 如果百位上数字为1，则百位上出现1的次数不仅受更高位影响，还受低位影响。如12113，则百位出现1的情况共有 1200+114=1314 个，也就是高位影响的 12 * 100 + 低位影响的 113+1 = 114 个。
	 *
	 * 如果百位上数字为其他数字，则百位上出现1的次数仅由更高位决定。如 12213，则百位出现1的情况为 (12+1)*100=1300。
	 *
	 * 有以上分析思路，写出下面的代码。其中 low 表示低位数字，curr 表示当前考虑位的数字，high 表示高位数字。一个简单的分析，考虑数字 123，则首先考虑个位，则 curr 为 3，低位为 0，高位为 12；然后考虑十位，此时 curr 为 2，低位为 3，高位为 1。其他的数字可以以此类推
	 *
	 * 作者：源码共读121
	 * 链接：https://www.jianshu.com/p/1582fbaf05f7
	 * 来源：简书
	 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
	 * @param n
	 * @return
	 */
	public int NumberOf1Between1AndN_Solution2(int n) {
		int count=0;
		//每10位循环一次
		
		for(int i = 1; i <= n; i *= 10){
		int a = n / i; // 高位
		int b = n % i; // 低位
		count += (a+8) / 10 * i;
		
		if(a % 10 == 1){
		count += b + 1;
		}
		} 
		return count;
	}
	
	public static int NumberOf1Between1AndN_Solution(int n) {
		long count=0;
		int i=1;
		int current=0,before=0,after=0;
		while( ( n/i) !=0){
			//高 ,当前, 低
			before  = n/(i*10);
			current = (n/i) % 10;
			after = n - (n / i) * i; // 低位
			if (current == 0)
				//如果为0,出现1的次数由高位决定,等于高位数字 * 当前位数
				count = count + before * i;
			else if(current == 1)
				//如果为1,出现1的次数由高位和低位决定,高位*当前位+低位+1,为什么要加1,因为当前数为1,所以必须加1
				count = count + before * i + after + 1;
			else if (current > 1)
				// 如果大于1,出现1的次数由高位决定,（高位数字+1）* 当前位数
				count = count + (before + 1) * i;
			i = i*10;

		}
		return (int) count;
    }

	public static void main(String[] args) {
		NumberOf1Between1AndN_Solution(13);
	}
}
